package lc_2517_礼盒的最大甜蜜度;

import java.util.Arrays;

public class Solution {

	public int maximumTastiness(int[] price, int k) {
		Arrays.sort(price);
		int n = price.length;
		int l = 0, r = price[n - 1] - price[0];
		while (l < r) {
			int m = ((r - l + 1) >> 1) + l;
			int cnt = 1, pre = price[0];
			for (int i = 1; i < n; i++) {
				if (price[i] - pre >= m) {
					cnt++;
					pre = price[i];
				}
			}
			if (cnt >= k) {
				l = m;
			} else {
				r = m - 1;
			}
		}
		return l;
	}

}